/**
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {string[][]}
 */
 const isDiff1 = function(w1,w2){
    let num = 0;
    for(let i = 0; i < w1.length; i++){
        if(w1[i] != w2[i]) num++;
        if(num > 1) return false;
    }
    return num == 1;
};
 var findLadders = function(beginWord, endWord, wordList) {
    if(!wordList.includes(endWord)) return [];
    const ansList = [];
    const map = {};
    const stepList = {};
    const wordStep = {};
    map[beginWord] = [];

    for(let i = 0; i < wordList.length; i++){
        map[wordList[i]] = [];
        if(isDiff1(wordList[i],beginWord)){
            map[beginWord].push(wordList[i]);
        }
        for(let j = 0; j < wordList.length; j++){
            if(j == i) continue;
            if(isDiff1(wordList[i],wordList[j])){
                map[wordList[i]].push(wordList[j]);
            }
        }
    }
    const stepCalc = function(nowWord,step){
        wordStep[nowWord] = step;
        for(let key of map[nowWord]){
            if(!wordStep[key] || wordStep[key] > step + 1){
                stepCalc(key,step+1);
            }
        }
    };
    stepCalc(beginWord,0);
    for(let key of wordList){
        if(!stepList[wordStep[key]]) stepList[wordStep[key]] = [];
        stepList[wordStep[key]].push(key);
    }
    const bfs = function(step,tarWord,ans){
        if(step === 0){
            if(isDiff1(beginWord,tarWord)){
                ansList.push([beginWord,...ans]);
            }
            return;
        }
        if(!stepList[step]) return;
        for(let key of stepList[step]){
            if(isDiff1(key,tarWord)){
                bfs(step-1,key,[key,...ans]);
            }
        }
    };
    bfs(wordStep[endWord] - 1,endWord,[endWord]);
    return ansList;
};